// https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
public class SortedArrayToBST {
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val)
        {
            this.val = val;
        }
    }
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            if(nums.length == 0) return null;
            return traversal(nums,0,nums.length-1);

        }

        private TreeNode traversal(int []  nums , int l, int r)
        {
            if(l > r) return null;
            int mid = l + (r - l ) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = traversal(nums,l,mid-1);
            root.right = traversal(nums,mid + 1,r);
            return root;
        }
    }
}
